import java.util.Arrays;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * <p>
 * 如果数组中不存在目标值，返回 [-1, -1]。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 * 示例 2:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6)));
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        if (nums.length == 0) return result;
        if (nums.length == 1) {
            if (target == nums[0]) {
                result[0] = 0;
                result[1] = 0;
            }
            return result;
        }
        int mid = nums.length / 2 - 1;
        for (int x = 0, y = nums.length; x < y - 1; ) {
            if (target == nums[mid]) {
                //往上找和往下找
                int pre = mid;
                for (; pre >= 0; pre--) {
                    if (nums[pre] != target) break;
                }
                int next = mid;
                for (; next < nums.length; next++) {
                    if (nums[next] != target) break;
                }
                result[0] = pre + 1;
                result[1] = next - 1;
                return result;
            } else if (target < nums[mid]) {
                // 往小了找
                y = mid;
                mid = mid != (x + mid) / 2 - 1 ? (x + mid) / 2 - 1 : (x + mid) / 2;
            } else {
                // 往大了找
                x = mid;
                mid = mid != (y + mid) / 2 - 1 ? (y + mid) / 2 - 1 : (y + mid) / 2;
            }
        }
        return result;
    }

}